package leetcode;

public class LC5 {
    /*
    给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
    找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
    返回容器可以储存的最大水量。
    说明：你不能倾斜容器。
    输入：[1,8,6,2,5,4,8,3,7]
    输出：49
    解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49

    思路：
    其实没有这么复杂，用分解问题的思路来理解就好了。
    这道题本质就是分解问题的思想，具有最优子结构，但是不具备重叠子问题性质，所以不是动态规划。
    假设maxArea(left, right)是[left, right]区间的最优盛水量，如果height[left] < height[right]，
    那么无论怎么向左移动right，都不可能得到比height[left] * (right - left)更优的解，
    这个很好想，大家想想应该就能明白，不用那么复杂的数学公式推导的。
    所以这个时候，最优解就是max(height[left] * (right - left), maxArea(left + 1, right))，
    相当于原问题的解是由子问题[left + 1, right]的解构成的，这就是最优子结构。因为对称性，
    如果height[left] > height[right]，那么原问题最优解就是子问题[left, right - 1]的解构成的。
    显然，分解问题以后具有很明显的递归性质，用递归来编程更容易理解，当然效率更低一点就是了，
    但是时间复杂度上是一样的，额外的开销在于递归栈的创建和销毁。本解法只做理解之用，本质上和双指针解法是一样的，只是不同的编程实现罢了。
     */
    public static void main(String[] args) {
        LC5 lc5 = new LC5();
        System.out.println(lc5.maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7}));
    }
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int max = 0;
        while(left < right){
            if(height[left] > height[right]){
                max = Math.max(max, (right - left) * height[right]);
                right--;
            }else {
                max = Math.max(max, (right - left) * height[left]);
                left ++;
            }
        }
        return max;
    }
}
